Data links in a communication network may generally support the transport of data from many simultaneous active flows. Each flow may, for example, correspond to a communications link from one internet protocol (“IP”) address to another IP address; however, this is not the only possible scenario (for example, traffic flows may also correspond to different types of data traffic, such as voice, data, video, etc., or classes of traffic having different priorities or quality of service (QoS); the invention is not limited to these examples). The traffic flows are generally not continuous; rather, they are generally bursty in nature. In many networks, multiple flows may seek to utilize a common communication resource; one example, to which the invention is not limited, is the case of multiple links to a routing node in a network.
Communication traffic is often furnished in a packetized fashion. The packetized nature of the data traffic often makes it simpler for a link capacity resource to be shared among several competing flows. Queues within routers may be used to buffer the incoming bursty flows. The shared link capacity resource may be managed by end-to-end congestion control and/or active queue management at network routers.
In many networks, a particular flow may have a committed information rate at which packet delivery is guaranteed (note that, while the discussion in this application is directed to packets and packetized information, the discussion is generally applicable to any information units (e.g., bytes, words, etc.)). If a flow transmits data faster than its committed information rate, the network may make an effort to accommodate this offending flow on a best effort basis, but may drop packets if the aggregate data rate from all the flows produces congestion (i.e., if the aggregate data rate exceeds capacity).
Various methods have been developed to select which packets to drop in order to eliminate congestion. Fair methods will assign drop probabilities to packets based on how much, if any, their incoming arrival rate exceeds their committed information rate.
Active queue management schemes for fair bandwidth allocation can be classified into two distinct categories, the core-stateful approach and core-stateless approach. The core-stateful approach requires the system associated with the shared resource (for example, but not limited to, a core router) to maintain per-flow state information, and is thus difficult to scale because of the large number of flows that may be present. In contrast, in the core-stateless queue management approach, the system does not need to maintain per-flow state information. Instead, per-flow information may be encoded in packet headers by other elements (for example, but not limited to, edge routers).
One idea used in some examples of core-stateless fair queuing (CSFQ) is to keep per-flow states at less-aggregated edge routers and to carry that information in packets to the core. Specifically, edge routers may measure or estimate each flow's arrival rate and label the packets of a flow with a corresponding arrival rate of the flow. Core routers may then estimate the flow fair share and probabilistically drop packets with labels (corresponding to arrival rates) larger than their estimated fair shares of the bandwidth. However, this requires that the core routers compute and maintain estimates of flow fair shares.
In a particular example, “differentiated services,” or DiffServ, is a recent proposal to provisioning QoS for IP networks, particularly, the Internet. Related to the DiffServ proposal is a desire to provide a means of offering a spectrum of services in the Internet without the need for per-flow state and signaling in every router. DiffServ differentiates its service priorities by classifying flows into the Expedited Forwarding (EF), the Assured Forwarding (AF), and the best effort forwarding classes through service contracts. In the past, multiple random early drop (MRED) is recommended for the management of queues that handle AF traffic. Although MRED may stabilize the router queue, and may eliminate network synchronization by randomization, MRED cannot provide fair bandwidth allocation among flows.